/**
 * 22. 括号生成
 * 中等
 * 相关标签
 * conpanies icon
 * 相关企业
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 *
 * 提示：
 *
 * 1 <= n <= 8
 */

/**
 * @param {number} n
 * @return {string[]}
 */
const generateParenthesis = function (n) {
  const res = []
  backtrack(res, '', 0, 0, n)
  return res
}

/**
 *
 * @param arr
 * @param cur
 * @param open 左括号个数
 * @param close 右括号个数
 * @param max
 */
function backtrack(arr, cur, open, close, max) {
  // 当前字符串长度为 最大括号数*2 则表明需终止
  if (cur.length === max * 2) {
    arr.push(cur)
    return
  }

  // 如果 左括号数 小于 max 说明还可以继续添加 (
  if (open < max) {
    backtrack(arr, cur + '(', open + 1, close, max)
  }

  // 如果 右括号数 小于 左括号数 说明还可以添加 )
  if (close < open) {
    backtrack(arr, cur + ')', open, close + 1, max)
  }
}

console.log(generateParenthesis(3))
